package jjn.round2;

/**
 * @author Jiang Jining
 * @since 2023-05-15 23:06
 */
public class Offer33_VerifyPostOrder {
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder, 0, postorder.length - 1);
    }
    
    private boolean helper(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int mid = left;
        int root = postorder[right];
        while (postorder[mid] < root) {
            mid++;
        }
        int temp = mid;
        while (temp < right) {
            if (postorder[temp++] < root) {
                return false;
            }
        }
        return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
    }
}
